package cn.edu.njust.alg.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_102_Binary_Tree_Level_Order_Traversal {
	public static List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (root == null) {
			return list;
		}
		Queue<TreeNode> q1 = new LinkedList<TreeNode>();
		Queue<TreeNode> q2 = new LinkedList<TreeNode>();
		Queue<TreeNode> tmp = null;
		q1.offer(root);
		while (!q1.isEmpty()) {
			List<Integer> inlist = new ArrayList<Integer>();
			while (!q1.isEmpty()) {
				TreeNode t = q1.poll();
				inlist.add(t.val);
				if (t.left != null) {
					q2.offer(t.left);
				}
				if (t.right != null) {
					q2.offer(t.right);
				}
			}
			list.add(inlist);
			tmp = q1;
			q1 = q2;
			q2 = tmp;
		}
		List<List<Integer>> relist = new ArrayList<List<Integer>>();
		for (int i = list.size() - 1; i >= 0; i--) {
			relist.add(list.get(i));
		}

		return relist;
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		levelOrder(root);
	}

}
